package airthmetic.exercise.dp;

public class _72_编辑距离 {

    public static int minDistance(String word1, String word2) {
        /**
         1.确定状态参数和选择决策
         状态参数是子问题与原问题之间不断变化的值。
         此题是：word1转成w1数组之后的索引   word2转成w2数组之后的索引
         选择/决策 通过选择使状态参数变化并逐渐趋近于原问题的解
         此题是:w1,w2下标的变化

         2.定于dp数组(dp table)的含义
         dp[n][m]表示需要做的最少操作数

         3.初始化dp数组
         此题的初始化状态就是word1 与word2空串 此时无需任何操作
         所以初始化dp[i][0] = 0  dp[0][j] = 0

         4.推导状态转移公式
         if(w1[i-1] == w2[j-1]){
         dp[i][j] = dp[i-1][j-1];
         }else{
         dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1;
         }
         */

        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int n = w1.length;
        int m = w2.length;
        int[][] dp = new int[n+1][m+1];
        for(int i=0; i<=n; i++){
            dp[i][0] = i;
        }
        for(int j=0; j<=m; j++){
            dp[0][j] = j;
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(w1[i-1] == w2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
//                    dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + 1;

                    dp[i][j] = min(dp[i-1][j] +1,
                            dp[i][j-1] +1,
                            dp[i-1][j-1] +1);
                }
            }
        }

        return dp[n][m];
    }

    public static void main(String[] args) {
        String s1 = "horse";
        String s2 = "ros";
        int i = minDistance(s1, s2);
        System.out.println(i);
    }

    public static int min(int x,int y,int z) {
        return Math.min(Math.min(x,y),z);
    }
}
